package com.example.Arithmetic.Lettcode;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * 日期：2024/1/1
 * 时间：11:05
 * 描述：力扣103,322零钱兑换
 * 类似完全背包问题，动态规划，求最小值
 */
public class E01Lettcode103 {
    public int coinChange(int[] coins, int amount) {
        int[] lq = new int[amount + 1];
//        第一行初始化
        Arrays.fill(lq, amount + 1);
        lq[0] = 0;
        for (int c : coins) {
            for (int i = c; i < amount + 1; i++) {
                lq[i] = Math.min(lq[i], 1 + lq[i - c]);
            }
        }
        return lq[amount] - amount > 0 ? -1 : lq[amount];
    }

        public int coinChange1(int[] coins, int amount) {
            Arrays.sort(coins);
            boolean allMultiply = true;

            for (int i = 1; i < coins.length; ++i) {

                if (coins[i] % coins[0] != 0) {
                    allMultiply = false;
                    break;
                }
            }

            if (allMultiply && (amount % coins[0]) != 0) {
                return -1;
            }

            int minCount = Integer.MAX_VALUE;
            int[] counts = new int[coins.length];
            int i = coins.length - 1;
            int count = amount / coins[i];
            int amount1 = amount - count * coins[i];

            if (amount1 == 0) {
                return count;
            }

            if (coins[0] * (count + 1) == amount) {
                return count + 1;
            }

            if (count == amount / coins[0]) {
                return -1;
            }

            counts[i] = count;
            amount = amount1;

            while (true) {
                if (count >= minCount || i <= 0) {
                    count -= counts[i];
                    amount += counts[i] * coins[i];

                    do {
                        ++i;

                        if (i >= coins.length) {
                            return minCount < Integer.MAX_VALUE ? minCount : -1;
                        }

                    } while (counts[i] == 0);
                    --counts[i];
                    --count;
                    amount += coins[i];
                }

                --i;
                counts[i] = 0;

                while (amount >= coins[i]) {
                    amount -= coins[i];
                    ++counts[i];
                }

                count += counts[i];

                if (amount == 0 && count < minCount) {
                    minCount = count;
                }
            }
        }
    @Test
    public void test() {
        int[] ints = new int[]{1, 2, 5};
        E01Lettcode103 e01Lettcode103 = new E01Lettcode103();
        System.out.println(e01Lettcode103.coinChange(ints, 100000000));
    }
    @Test
    public void test1() {
        int[] ints = new int[]{1, 2, 5};
        E01Lettcode103 e01Lettcode103 = new E01Lettcode103();
        System.out.println(e01Lettcode103.coinChange1(ints, 100000000));
    }
}

